Ban đầu, Bedtime Stories là thành quả hợp tác giữa Madonna và Shep Pettibone và có phong cách gần giống với album trước đó là Erotica (1992). Tuy nhiên, theo như mong ước của Madonna về việc làm "mềm mại" hình ảnh của cô trong mắt công chúng, cũng như sự ngưỡng mộ của cô với album Pendulum Vibe của ca sĩ Joi, cô quyết định thay đổi phong cách âm nhạc với những âm thanh thân thiện với các đài phát thanh và đậm chất R&B đương đại hơn. Cô cũng gửi lời cảm ơn đến Pettibone vì đã có sự "thấu hiểu", và đây là lần cuối cùng mà nữ ca sĩ hợp tác với ông. Cũng trong thời gian này, Madonna vẫn tiếp tục theo đuổi hình ảnh gợi cảm và khiêu khích nhưng với mức độ "dễ thở" hơn nhiều so với những năm đầu thập niên 1990 với hai video ca nhạc "Justify My Love" và "Erotica" bị cấm chiếu trên MTV và cuốn sách Sex gây nhiều tranh cãi về nội dung.

Trong khi album được cho là dễ nghe hơn và lời ca ít gây sốc hơn so với album trước, Bedtime Stories vẫn ẩn chứa sự đương đầu, thách thức của nữ ca sĩ. "Human Nature" như là một lời bình cay độc của Madonna hướng tới giới truyền thông vì cách họ đối xử với cô trong suốt thời gian trước với những lời ca như: "Tôi nói điều gì sai ư? Ôi không, tôi chẳng biết rằng mình không được phép nói về tình dục" ("Did I say something wrong? Oops, I didn't know I couldn't talk about sex"). Ngoài ra, mặc dù Madonna cũng nỗ lực làm mới hình ảnh của mình nhưng cô cũng nói rằng lúc này là một "thời kỳ trả đũa" tất cả những con người đã từng cố xâm phạm đời tư của cô và hy vọng rằng họ nên dừng lại và tập trung vào âm nhạc của cô.

Bedtime Stories là một trong số rất ít những album mà Madonna hợp tác với nhiều nhà sản xuất danh tiếng (ngoại lệ là Nile Rodgers với Like a Virgin, David Foster với Something to Remember và Timbaland, Pharrell và Nate "Danja" Hills với Hard Candy). Album có sự tham gia viết lời và sản xuất từ Dallas Austin, lúc bấy giờ đã được công chúng biết đến qua những tác phẩm hợp tác với TLC; Babyface, người đã từng làm việc với Whitney Houston và Toni Braxton; Dave Hall, nhà sản xuất đã từng tham gia vào nhiều bản hit của Mariah Carey; và nữ ca sĩ người Iceland Björk, người đồng sáng tác với Madonna bài hát cùng tên album.